package algorithm.leetcode.I401to600;

import java.util.Collections;
import java.util.List;

public class Q524 {

    public String findLongestWord(String s, List<String> dictionary) {
        // 需要输出长度最长and字典序最小的唯一一个结果
        Collections.sort(dictionary);
        String result = "";
        for (String target : dictionary) {
            if (canConvert(s, target) && target.length() > result.length()) result = target;
        }
        return result;
    }

    public boolean canConvert(String s, String t) {
        int sIndex = 0, tIndex = 0;

        while (sIndex < s.length() && tIndex < t.length()) {
            if (s.charAt(sIndex) == t.charAt(tIndex)) tIndex++;
            sIndex++;
        }

        return tIndex == t.length() && sIndex <= s.length();
    }

}
